Locally decodable code

A locally decodable code is an error-correcting code that allows to decode a single bit of a message with high probability by only looking at a small number of bits of a possibly partially corrupted codeword.[1][2] The related locally testable codes merely require that it can be locally detected whether a given message is close to a codeword, and in this sense locally decodable codes are a special case of locally testable codes.

More formally, a q-query locally decodable code encodes an n-bit message x by an N-bit codeword C(x) such that any bit x_i of the message can be probabilistically recovered by querying only q bits of the codeword C(x), even if some constant fraction of the codeword has been corrupted.

Examples

The Walsh–Hadamard code WH is a simple, locally decodable code. It has an optimal q=2 queries and a best possible decoding error. However, codewords of n-bit messages have exponential length N=2^n, which is why the Walsh–Hadamard code has a very inefficient rate. If a received signal y\in\{0,1\}^N agrees with some codeword WH(x) for some message x\in\{0,1\}^n on at least a 1-\delta fraction of bits, then x_i can be recovered from y with probability 1-2\delta.[3]

References

  1. ^ Rafail Ostrovsky, Omkant Pandey, Amit Sahai. "Private Locally Decodable Codes". http://eprint.iacr.org/2007/025.pdf. 
  2. ^ Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, Technical Report ECCC TR06-127, 2006.
  3. ^ Section 11.5.2 of Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge. ISBN 978-0-521-42426-4. http://www.cs.princeton.edu/theory/complexity/ 

See also